package com.interview.javabase.algorithm;

import org.junit.Test;
import org.springframework.boot.test.context.SpringBootTest;

/**
 * @description:
 * @author: zhangshuguang@vichain.com
 * @date: 2019/06/12 15:19
 */
@SpringBootTest
public class Demo6 {

    @Test
    public void solution1() {
        ListNode listNode = new ListNode(3);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(0);
        ListNode listNode3 = new ListNode(-4);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode1;

        System.out.println(hasCycle(listNode));

        System.out.println(findBeginLoop(listNode).val);
        System.out.println(circleLength(listNode));
    }

    @Test
    public void solution2() {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        listNode.next = listNode1;
        listNode1.next = listNode;

        System.out.println(hasCycle(listNode));

        System.out.println(findBeginLoop(listNode).val);
        System.out.println(circleLength(listNode));
    }

    /**
     * 判断是否存在环
     * @param head
     * @return
     */
    private boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode l1 = head.next, l2 = head.next.next;
        while (l1 != null && l2 != null && l2.next.next != null) {
            if (l1 == l2) {
                System.out.println("l1=" + l1.val + "****" + "l2=" + l2.val);
            }
            l1 = l1.next;
            l2 = l2.next.next;
        }
        return false;
    }

    /**
     * 寻找环入口
     * @param head
     * @return
     */
    private static ListNode findBeginLoop(ListNode head) {

        ListNode slowPtr = head;
        ListNode fastPtr = head;
        boolean loopExists = false;

        if (head == null) {
            return null;
        }

        while (slowPtr.next != null && fastPtr.next.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr) {
                loopExists = true;
                System.out.println("slowPtr=" + slowPtr.val + "****" + "fastPtr=" + fastPtr.val);
                break;
            }
        }
        // 环存在
        if (loopExists) {
            slowPtr = head;
            while (slowPtr != fastPtr) {
                slowPtr = slowPtr.next;
                fastPtr = fastPtr.next;
            }
            return slowPtr;
        }
        // 环不存在
        return null;
    }


    /**
     * 求单链表环的长度
     * @param head
     * @return
     */
    private static int circleLength(ListNode head) {
        // 找到环的入口结点
        ListNode p = findBeginLoop(head);

        // 不存在环时，返回0
        if (p == null) {
            return 0;
        }

        ListNode q = p.next;
        int length = 1;
        while (p != q) {
            length++;
            q = q.next;
        }
        // 返回环的长度
        return length;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

    }
}
